Volume rendering is an important branch of computer graphics, following behind the development of geometric rendering and pixel rendering. Volume rendering refers to the direct rendering of a volume data set to show the characteristics of the interior of a solid object when displayed on a 2D graphics device. A volume data set is a three-dimensional array of voxels. Voxels have been defined as sample points separated by a finite distance. Each voxel has a position and a value. The voxel position is a three-tuple specifying an x, y, and z position within the 3D voxel array. The voxel value depends upon its format. For example, a voxel has an intensity element and may have an index element. These elements are usually treated differently in the volume rendering process. The collection of values for all points in the volume is called a scalar field on the volume.
Volume data sets can be generated by numerous means, but most commonly by some method of 3D scanning or sampling and by numerical modeling. For example, a volume data set may be generated by Magnetic Resonance Imaging, or MRI, wherein the density of human or animal tissue is computed at each point of a 3D grid. A display of this information could indicate the boundaries of the various types of tissue, as indicated by density changes. Volume rendering is the process of displaying this data on a 2D graphics device.
The very first voxel in a volume data set with the coordinates (0,0,0) is considered to be the origin of the volume data set. The three coordinates, in order, correspond to the column, row, and slice of the image in the volume data set.
Volume data sets can be quite large and thus can place a strain on system resources. For example, a typical volume data set from a MRI scanner may contain 6.7 million voxels or more, whereas polygon data sets for geometric rendering typically contain less than 1/2 million polygons. Thus, there is a much greater need for hardware acceleration when rendering volumes.
In volume rendering there is often a need to be able to view the rendered image from various orthographic and perspective projections. Studies have shown that when viewing such renderings over long periods of time, perspective views are less strenuous on the observer than are orthographic views. Also, perspective renderings often give a better visual cue for spacial perception than orthographic renderings. Thus, a key step in the volume rendering process is the 3D spatial volume transformation of the original volume data set for orthographic or perspective rendering. Typical types of transformations required for both orthographic or perspective rendering may include zoom, pan, rotation, and even shear of the input volume for projection into an output raster type display device. Once a transformation has been done, various resampling techniques must be applied, such as nearest neighbor or trilinear interpolation, to determine pixel values for rendering.
Typically, a perspective view of a volume data set is realized by depicting objects that are farther away from the viewer as being smaller than objects that are closer to the viewer. Geometric objects are rendered in perspective by dividing x, y, and z locations of vertices of the geometric object by the w, or homogeneous coordinate, after a model and view transformation have been performed. In addition, the homogeneous coordinate w modulates the degree of perspective distortion.
Geometric objects and volume voxels can be transformed and depicted in a perspective view through the following steps. First, a source space vertex having (x,y,z) coordinates is converted to a homogeneous coordinate to allow for matrix multiplication as shown below: ##EQU1##
An orthographic model-view matrix is multiplied by a perspective matrix to obtain a combined matrix as shown below: ##EQU2##
In the perspective matrix, aP=(2*zNear)/(right-left), fP=(2*zNear)/(top-bottom), iP=(right+left)/(right-left), jP=(top+bottom)/(top-bottom), kP=(zFar+zNear)/(zFar-zNear), and oP=(2*zFar*zNear)/(zFar-zNear). (left, bottom, -zNear) and (right, top, -zNear) specify points on the near clipping plane that are mapped to the lower left and upper right corners of the window, assuming that the eye point of the viewer is located at (0,0,0). The far clipping plane location is specified by -zFar. Both zNear and zFar must be positive.
In order to transform the source space vertex from source space to destination space, the source vertex in matrix form is multiplied by the combined matrix to yield the destination space vertex as shown below: ##EQU3##
Performing matrix multiplication, the values for x', y', z', and w' of the vertex point in destination space are derived as shown below: EQU x'=(a * x)+(e * y)+(i * z)+m EQU y'=(b * x)+(f * y)+(j * z)+n EQU z'=(c * x)+(g * y)+(k * z)+o EQU w'=(d * x)+(h * y)+(l * z)+p
Next, the vertex point (x',y',z',w') in destination space is divided by the homogeneous coordinate `w` to modulate the perspective distortion as shown below: EQU x'=X'/w' EQU y'=y'/w' EQU z'=z'/w' EQU w'=w'/w'=1
The x' and y' coordinates can now be further adjusted, if desired, for final rendering and sent to the frame buffer.
Two mapping approaches have been utilized for such transformations. A forward mapping approach, which was used in the description above, takes the source vertex and transforms it via a transformation matrix to fit into the destination space. In a backward mapping, or inverse transformation approach, each destination vertex is transformed via an inverse transformation matrix and resampled from the source space. Forward mapping runs the risk of leaving "holes" in the rendering because the source space is sometimes smaller than the destination space. Inverse transformation lends itself to the technique of "ray casting," or stepping in the z-direction, which eliminates the "holes" problem because sample points are taken from the larger destination space back to the smaller source space.
The geometric perspective method of rendering volume data sets in perspective view is very computation intensive and most difficult to do. Because of the typically large size of volume data sets, 3D spatial transformations and perspective renderings are quite taxing on system resources. Optimization of the process is thus a continuing and challenging need in the art. Both hardware and software oriented optimization solutions are beneficial. Current methods of 3D spatial transformation and perspective rendering that utilize floating point numbers are quite expensive, especially when division and often times multiplications are involved. Repetitious calculations for each sample point are also very costly in terms of time to render.
A 3D texture mapping technique supports a limited form of volume rendering that can be modified to yield perspective views. Each successive texture mapped slice of the volume can be adjusted by a 2D scale or zoom operation to reduce the size of the object as you step in the z-direction to obtain perspective. However, this approach is not very accurate.
There is thus a need in the art for a method of 3D spatial transformation and perspective view volume rendering that overcomes the deficiencies of the classic geometric perspective and 3d texture mapping methods by utilizing a ray transform approach that makes fewer compromises in quality or accuracy. There is a need for a perspective view volume rendering method that reduces the number of floating point calculations required to render a perspective view, especially division and multiplication. Also, there is a need in the art to utilize faster integer calculations, such as addition and subtraction, and other simpler CPU instructions, such as shifts and masks. There is a further need in the art to eliminate repetitious calculations from the process. There is also a need in the art to utilize both hardware and software optimization techniques. There is a further need in the art to utilize an inverse transformation approach to perspective view volume rendering to eliminate "holes" in the rendered image. It is therefore apparent that there is a need for an improved method for a fast perspective view volume rendering which meets these and other needs in the art.
This application is related to application Ser. No. 08/866,859 filed May 30, 1997 entitled Fixed-Point Method for Fast and Precise 3D Spatial Transformations of Shaz Nagvi, Barthold Lichtenbelt, and Russell Huonder, which is incorporated herein by reference for all that is disclosed and taught therein.